package data.structure.tree.binary.search;


import data.structure.linear.queue.Queue;
import data.structure.tree.binary.search.printer.BinaryTreeInfo;
import data.structure.tree.binary.search.printer.BinaryTrees;

import java.util.Comparator;
import java.util.LinkedList;


/**
 * @Author douhy
 * @description 手写二叉搜索树
 * @date 22/01/29
 */
public class BinarySearchTree<E> implements BinaryTreeInfo {

    private int size;
    private Node<E> root;
    private Comparator<E> comparator;

    @Override
    public Object root() {
        return root;
    }

    @Override
    public Object left(Object node) {
        return ((Node<E>) node).left;
    }

    @Override
    public Object right(Object node) {
        return ((Node<E>) node).right;
    }

    @Override
    public Object string(Object node) {
        Node<E> myNode = (Node<E>) node;
        String parentString = "null";
        if (myNode.parent != null) {
            parentString = myNode.parent.element.toString();
        }
        return myNode.element + "_p(" + parentString + ")";
    }

    @Override
    public String toString() {
        return "BinarySearchTree{" +
                "size=" + size +
                ", root=" + root +
                ", comparator=" + comparator +
                '}';
    }

    // 元素访问抽象类(访问器)  访问者模式
    public static abstract class Visitor<E> {
        // 是否停止遍历变量
        boolean stop;

        // 访问接口 返回true表示结束循环
        abstract boolean visit(E element);
    }

    private static class Node<E> {
        E element;
        Node<E> parent;
        Node<E> left;
        Node<E> right;

        public Node(E element, Node parent) {
            this.element = element;
            this.parent = parent;
        }

        // 是否为叶子节点
        public static boolean isLeaf(Node node) {
            return node.left == null && node.right == null;
        }

        // 两个子节点
        public boolean hasTwoChildren() {
            return left != null && right != null;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "element=" + element.toString() +
                    '}';
        }
    }

    public BinarySearchTree() {
        this(null);
    }

    public BinarySearchTree(Comparator comparator) {
        this.comparator = comparator;
    }

    private int size() {
        return size;
    }

    private void clear() {
        root = null;
        size = 0;
    }

    private boolean isEmpty() {
        return size == 0;
    }

    // 元素空检查
    private void elementNotNullCheck(E element) {
        if (element == null) throw new IllegalArgumentException("element must not be null");
    }

    /**
     * 获取节点
     * @author Douhy
     * @date 2022/3/8
     * @param element
     * @return data.structure.tree.binary.search.BinarySearchTree.Node<E>
     */
    private Node<E> node(E element) {
        elementNotNullCheck(element);

        // 拿到root节点
        // 二分遍历
        Node<E> node = root;
        do {
            int compare = compare(element, node.element);
            if (compare > 0) {
                node = node.right;
            } else if (compare < 0) {
                node = node.left;
            } else { // 等于
                return node;
            }
        } while (node != null);

        return null;
    }

    /**
     * 是否包含某元素
     * @author Douhy
     * @date 2022/3/8
     * @param element
     * @return boolean
     */
    private boolean contains(E element) {
        return node(element) != null;
    }

    /***
     * 添加
     * @author Douhy
     * @date 2022/3/8
     * @param element
     * @return void
     */
    private void add(E element) {
        elementNotNullCheck(element);

        if (root == null) {
            root = new Node<>(element, null);
            size++;
            return;
        }

        Node<E> parent = root;
        Node<E> node = root;
        int cmp = 0;
        while (node != null) {
            parent = node;
            cmp = compare(element, node.element);
            if (cmp > 0) {
                node = node.right;
            } else if (cmp < 0) {
                node = node.left;
            } else {
                node.element = element;
                return;
            }
        }

        Node<E> newNode = new Node<>(element, parent);
        if (cmp > 0) {
            parent.right = newNode;
        } else {
            parent.left = newNode;
        }
        size++;

    }

    // 前序遍历
    public void preorderTraversal(Visitor visitor) {
        preorderTraversal(root, visitor);
    }

    // 前序遍历
    public void preorderTraversal(Node<E> node, Visitor visitor) {
        if (node == null || visitor.stop) return;

        visitor.stop = visitor.visit(node.element);
        preorderTraversal(node.left, visitor);
        preorderTraversal(node.right, visitor);
    }

    // 中序遍历
    public void inorderTraversal(Visitor<E> visitor) {
        inorderTraversal(root, visitor);
    }

    // 中序遍历
    public void inorderTraversal(Node<E> node, Visitor<E> visitor) {
        if (node == null || visitor.stop) return;
        inorderTraversal(node.left, visitor);
        if (visitor.stop) return;
        visitor.stop = visitor.visit(node.element);
        inorderTraversal(node.right, visitor);
    }

    // 后续遍历
    public void postorderTraversal(Visitor<E> visitor) {
        postorderTraversal(root, visitor);
    }

    // 后续遍历
    public void postorderTraversal(Node<E> node, Visitor<E> visitor) {
        if (node == null || visitor.stop) return;
        postorderTraversal(node.left, visitor);
        postorderTraversal(node.right, visitor);
        if (visitor.stop) return;
        visitor.stop = visitor.visit(node.element);
    }

    // 层序遍历
    public void leverOrderTraversal(Visitor<E> visitor) {
        if (root == null || visitor.stop) return;
        Queue<Node<E>> queue = new Queue<>();
        queue.enQueue(root);

        while (!queue.isEmpty()) {
            Node<E> node = queue.deQueue();
            if (visitor.visit(node.element)) return;
            if (node.left != null) {
                queue.enQueue(node.left);
            }
            if (node.right != null) {
                queue.enQueue(node.right);
            }
        }

    }

    /**
     * @return 返回值等于0，代表e1和e2相等；返回值大于0，代表e1大于e2；返回值小于于0，代表e1小于e2
     */
    private int compare(E e1, E e2) {
        if (comparator != null) {
            return comparator.compare(e1, e2);
        }
        return ((Comparable<E>) e1).compareTo(e2);
    }

    // 计算二叉树某个节点高度
    public static int height(Node node) {
        if (node == null) return 0;
        return 1 + Math.max(height(node.left), height(node.right));
    }

    // 计算二叉树高度 层序遍历方式
    public static int heightRoot(Node root) {
        if (root == null) return 0;
        Queue<Node> queue = new Queue<>();
        queue.enQueue(root);
        int height = 1;
        int size = 1;
        while (!queue.isEmpty()) {
            Node node = queue.deQueue();
            size--;
            if (node.left != null) {
                queue.enQueue(node.left);
            }
            if (node.right != null) {
                queue.enQueue(node.right);
            }
            if (size == 0) {
                height++;
            }
        }
        return height;
    }

    // 是否为完全二叉树
    public static boolean isComplete(Node root) {
        // 层序遍历
        Queue<Node> queue = new Queue();
        queue.enQueue(root);
        // 标记位  后序节点必须都是叶子结点 否则非完全二叉树
        boolean leaf = false;

        while (!queue.isEmpty()) {
            Node node = queue.deQueue();

            if (leaf && !node.isLeaf(node)) return false;

            if (node.left != null) {
                queue.enQueue(node.left);
            } else if (node.right != null) { // node.left == null && node.right != null
                return false;
            }

            if (node.right != null) {
                queue.enQueue(node.right);
            } else {
                leaf = true;
            }
        }
        return true;

    }

    // 反转二叉树
    public static Node reversalBinaryTree(Node root) {
        if (root == null) return null;
        Queue<Node> queue = new Queue();
        queue.enQueue(root);
        while (!queue.isEmpty()) {
            LinkedList<Node> linkedList = new LinkedList();
            Node node = queue.deQueue();

            if (node.left != null) {
                queue.enQueue(node.left);
            }

            if (node.right != null) {
                queue.enQueue(node.right);
            }

            Node temp = node.left;
            node.left = node.right;
            node.right = temp;

        }
        return root;
    }

    // 获取前驱节点
    public Node predecessor(Node node) {
        if (node == null) return null;

        // 说明 存在左子树 node.left.right.right.....
        if (node.left != null) {
            node = node.left;
            while (node.right != null) {
                node = node.right;
            }
            return node;
        }

        while (node.parent != null && node.parent.left == node) {
            node = node.parent;
        }
        return node.parent;
    }

    // 获取后继节点
    public Node<E> successor(Node node) {
        if (node == null) return null;

        // 说明 存在左子树 node.left.right.right.....
        if (node.right != null) {
            node = node.right;
            while (node.left != null) {
                node = node.left;
            }
            return node;
        }

        while (node.parent != null && node.parent.right == node) {
            node = node.parent;
        }
        return node.parent;
    }

    private void remove(E element){
        remove(node(element));
    }

    /***
     * 删除元素
     * @author Douhy
     * @date 2022/3/8
     * @param node
     * @return void
     */
    private void remove(Node<E> node){
        if (node == null) return;
        size--;

        // 两个子节点 拿到后继节点 覆盖参数节点
        if (node.hasTwoChildren()){
            Node<E> s = successor(node);
            node.element = s.element;
            node = s;
        }

        Node<E> replacement = node.left != null ? node.left : node.right;

        // 说明存在左或者右子节点(node为1 的节点)
        if (replacement != null){
            replacement.parent = node.parent;

            if (node.parent == null){
                root = replacement;
            }else if (node == node.parent.left){
                node.parent.left = replacement;
            }else if (node == node.parent.right){
                node.parent.right = replacement;
            }

        }else if(node.parent == null){ // 根节点
            root = null;
        }else if(node.parent != null){ // 非根节点的叶子节点
            if (node.parent.left == node) node.parent.left = null;
            if (node.parent.right == node) node.parent.right = null;
        }
    }

    public static void main(String[] args) {
        BinarySearchTree<Integer> bst = new BinarySearchTree<>(new Comparator<Integer>() {
            public int compare(Integer o1, Integer o2) {
                return o1 - o2;
            }
        });

        bst.add(79);
        bst.add(68);
        bst.add(30);
        bst.add(89);
        bst.add(7);
        bst.add(48);
        bst.add(1);
        bst.add(74);
        bst.add(71);

       /* BinaryTrees.print(bst);
        System.out.println();
        System.out.println("=====================================================前序遍历开始====================================================");
        bst.preorderTraversal(new Visitor() {
            @Override
            boolean visit(Object element) {
                System.out.println(element);
                if (element.toString().equals("1"))
                    return true;
                else return false;
            }
        });

        System.out.println("=====================================================中序遍历开始====================================================");
        bst.inorderTraversal(new Visitor<Integer>() {
            @Override
            boolean visit(Integer element) {
                System.out.println(element);
                if (element.toString().equals("30"))
                    return true;
                else return false;
            }
        });

        System.out.println("=====================================================后序遍历开始====================================================");
        bst.postorderTraversal(new Visitor<Integer>() {
            @Override
            boolean visit(Integer element) {
                System.out.println(element);
                if (element.toString().equals("1"))
                    return true;
                else return false;
            }
        });


        System.out.println("=====================================================层序遍历开始====================================================");
        bst.leverOrderTraversal(new Visitor<Integer>() {
            @Override
            boolean visit(Integer element) {
                System.out.println(element);
                if (element.toString().equals("30"))
                    return true;
                else return false;
            }
        });

        System.out.println("=====================================================计算二叉树某节点高度开始====================================================");
        System.out.println(height(bst.root));


        System.out.println("=====================================================计算二叉树高度开始====================================================");
        System.out.println(height(bst.root));

        System.out.println("=====================================================是否为完全二叉树====================================================");
        System.out.println(isComplete(bst.root));
*/
//        System.out.println("=====================================================反转二叉树前====================================================");
//        BinaryTrees.print(bst);
//        System.out.println();
//
//        Node node = reversalBinaryTree(bst.root);
//        bst.root = node;
//        System.out.println("=====================================================反转二叉树后====================================================");
//        BinaryTrees.print(bst);
//        System.out.println();

//        BinaryTrees.print(bst);
//        System.out.println();
//        System.out.println("=====================================================获取前驱节点====================================================");
//        System.out.println(bst.predecessor(bst.root));
//
//        System.out.println("=====================================================获取后继节点====================================================");
//        System.out.println(bst.successor(bst.root));

        BinaryTrees.print(bst);
        System.out.println();
        System.out.println("=====================================================删除节点测试====================================================");
        bst.remove(30);
        BinaryTrees.print(bst);
        System.out.println();
    }


}
